import java.util.ArrayList;
import java.util.List;

/**
 * Created by zhourh on 2018/8/2.
 * 请考虑一颗二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。

 如果有两颗二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。

 如果给定的两个头结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。
 *
 */
public class LeafSimilarTrees {

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(99);
        root1.left = new TreeNode(6);
        root1.left.left = new TreeNode(109);
        root1.left.right = new TreeNode(77);
        root1.left.left.right = new TreeNode(57);
        root1.left.right.left = new TreeNode(92);
        root1.left.right.right = new TreeNode(2);
        root1.left.left.right.left = new TreeNode(118);
        root1.left.left.right.right = new TreeNode(113);

        TreeNode root2 = new TreeNode(87);
        root2.left = new TreeNode(75);
        root2.left.left = new TreeNode(118);
        root2.left.right = new TreeNode(12);
        root2.left.right.left = new TreeNode(65);
        root2.left.right.right = new TreeNode(2);
        root2.left.right.left.left = new TreeNode(113);
        root2.left.right.left.right = new TreeNode(92);

        System.out.println(new LeafSimilarTrees().leafSimilar(root1, root2));

    }

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        } else if (root1 == null || root2 == null) {
            return false;
        }

        List<Integer> leafs1 = new ArrayList<>();
        List<Integer> leafs2 = new ArrayList<>();

        getLeafs(root1, leafs1);
        getLeafs(root2, leafs2);

        return leafs1.equals(leafs2);
    }

    public void getLeafs(TreeNode node, List<Integer> leafs) {

        if (node == null || leafs == null) {
            return;
        }

        if (node.left == null && node.right == null) {
            leafs.add(node.val);
            return;
        }

        if (node.left != null) {
            getLeafs(node.left, leafs);
        }

        if (node.right != null) {
            getLeafs(node.right, leafs);
        }
    }

}
